Software developers typically follow a work cycle of development, debugging, and testing of code. The productivity of a software developer can be improved by reducing the time spent in any part of the development cycle. Development and debugging productivity primarily depends on compilation time. Test productivity predominately depends on the efficiency of the executable code. Therefore it is important to continue to create compiler optimization tools that improve compilation and code generation, while producing code which can be fully debugged.
Almost all microprocessors have a load-store architecture in which values are loaded from memory into registers, operations are performed on values loaded in the registers, and the resulting values are again stored into memory. Accordingly, register allocation is an important technique of compiler optimization because the number of computer registers is limited and because register operations are performed faster than memory loads and stores.
There are a number of methods of optimizing register allocation. One method, either via profiling or by means of heuristic analysis, determines the relative benefit to be achieved by reducing the number of memory operations during register allocation. For instance, variables that are included in a nested software loop are prime candidates for optimizing register allocation. Variables used in inner loops are usually better candidates for optimizing register allocation than outer loops since typically more execution time is spent in inner loops than outer loops.
Another method for optimizing register allocation is global optimization via graph coloring. Graph coloring techniques allocate a color for each available computer register and determine whether the same register, represented by a graph color, may be used at different times by more than one value. The graph coloring technique is typically applied to an intermediate representation of the code, and according to the technique if a code instruction uses a value, the value is referred to as live during the time period in which the code instruction is executed. The range of code instructions in which the value is live is referred to as a live range of the value. While a value is live it is desirable to allocate a register to the value to enable instruction processing to continue without storing the value in memory. However, if there are more values requiring register allocation than available hardware registers, some of the values must be temporarily stored in memory and this situation is referred to as spill. The goal of register allocation is to allocate hardware registers to each value in a code segment while reducing or eliminating spill.
The graph coloring technique operates on values which may reside in virtual registers. Virtual registers may represent hardware registers, and it is assumed that there are an unlimited number of virtual registers available. As used herein the phrase computer registers, represents those registers that are visible to the software developer.
Coalescing is a technique that eliminates or reduces spill by exploiting opportunities to merge variables and thereby reduce the number of variables requiring register allocation. For instance, if two variables are required to be in computer registers at the same time, coalescing techniques determine whether the variables actually consist of the same value. If the two variables consist of the same value they need not be located in different computer registers.
Since variables may be merged during coalescing, another problem with past coalescing techniques is that the coalesced variable may not accurately represent the value that was originally associated with the variable, and therefore the software developer may be prevented from getting accurate debugging information about the coalesced variables. Consequently prior art coalesced code is seldom amenable to debugging. Yet, another problem with past coalescing is that fully coalesced variables require multiple iterations of the user code to compute the global data flow and often use techniques such as interference graphs. An interference graph is a pictorial representation of the relationship between the values and the instructions in which the values are used or defined and the interference graph is used to determine whether a variable may share a register with another variable. Iterative analysis cycles such as are typically required with the use of interference graphs employ expensive computer resources.
Prior art global register allocation was defined by John Cocke as described by, F. E. Allen and J. Cocke, A Program Data Flow Analysis Procedure, Association for Computing Machinery, Inc., Vol. 19, No. 3, 137-147 (1976). An early implementation was completed by Gregory Chaitin as described in, Register Allocation and Spilling via Graph Coloring, U.S. Pat. No. 4,571,678. A typical prior art global register allocation design was developed by Preston Briggs and is discussed in his Ph. D. Thesis from the Department of Computer Science at Rice University, Register Allocation via Graph Coloring, at pp. 14-16, 1992.
As known to those skilled in the art, coalescing problems such as retaining large numbers of live ranges and large interference graphs that increase the computer overhead necessary for processing, the inability to use coalesced results with debugging tools, and other related difficulties with coalescing for compilers and dynamic software development tools, such as debugging tools, have resulted in limitations on the further improvement of software development techniques.